1. Field of the Invention
This invention relates generally to techniques for processing image data, and relates more particularly to a system and method for effectively performing wavelet transform on incomplete data and applying it in image processing tasks.
2. Description of the Background Art
Wavelet transform is a representation of signal as a weighted sum of some orthonormal basis functions that is called wavelet basis. The corresponding weights are called wavelet coefficients. Haar and Daubechies are among the most frequently used wavelet bases. Wavelet transform has a property to de-correlate image signals, i.e., most of wavelet coefficients obtained are zeros or near zero. Given such a nice property, wavelet transforms are often used in various image processing tasks including, but not limited to, compression, denoising, and demosaicing. More detailed information describing wavelet transform and various techniques for performing wavelet transform procedures may be found in “A Wavelet Tour Of Signal Processing” by S. Mallat, published by Academic Press, 1999.
In many image processing tasks, image data may be incomplete. In other words, there are some missing values on certain pixel locations. For example, a full color image sensor is usually overlaid with a color filter array (CFA). In a CFA, only one color per pixel is measured. There are several different configurations of CFA. The most popular CFA is the Bayer pattern as described by B. E. Bayer in “Color Imaging Array”, U.S. Pat. No. 3,971,065, Jul. 20, 1976. It consists of three colors: red, green, and blue. Among all pixels, there are 25% red, 50% green, and 25% blue pixels. In order to improve color reproduction accuracy, T. Mizukura et al. proposed a four-color CFA in “Image pick-up device and image pick-up method adapted with image pick-up sensitivity”, U.S. Pat. No. 7,489,346, Feb. 10, 2009. Yoshihara et al. proposed to arrange the Bayer colors in a zigzag arrangement instead of a rectangular array, which improves fill factor and pixel sensitivity as described in “A 1/1.8-inch 6.4 MPixel 60 frames/s CMOS Image Sensor With Seamless Mode Change”, IEEE J. Solid-State Circuits, Vol. 41, No. 12, December 2006, pp. 2998-3006.
Demosaicing is a digital image process to reconstruct a full color image from the incomplete color samples output from an image sensor overlaid with a CFA. However, such reconstruction procedure provides only estimates of missing color values at certain pixel locations. The estimated values are usually different from the true color values supposed to be recorded. Such errors will propagate if we perform image processing tasks on the full color images reconstructed by domasaicing. Therefore, there is inherent advantage for performing various image processing techniques including wavelet transform directly on incomplete image data such as the output of an image sensor overlaid with a CFA. In order to perform wavelet transforms on incomplete data, a specially designed wavelet transform is needed since original wavelet transforms are based on the assumption of complete image data.
On the other hand, measuring local image similarity is another important problem in image processing. A better local image similarity measurement would improve the performance of many image processing tasks including, but not limited to, compression, denoising, and demosaicing. Image similarity can be categorized into 3 classes: 1) Low level similarity. Local image patches are considered to be similar if some distance metric (e.g. p-norm, EarthMovers, Mahalanobis) is less than a given threshold; 2) Mid-level similarity. Here local image patches share some simple semantic property; and 3) High-level similarity. In this case, similarity is primarily defined by semantics. Properties that make two patches similar are not visual but they can be inferred from visual information such as a gesture. More detailed information may be found in “Learning Task-Specific Similarity, PhD Thesis,” by Greg Shakhnarovich, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2005.
One important part of local image similarity measurement is to select an appropriate similarity metric. There are many existing metrics for low-level image similarity in the literature. For instance, one quite popular metric is based on Euclidean distance (L2 norm) between pixels as described by C. Tomasi and R. Manduchi in “Bilateral Filtering for Gray and Color Images,” Proc. of IEEE International Conference on Computer Vision, pp. 841-846, 1998. However, this metric is very sensitive to lighting conditions and noise. More robust patch-based Euclidean distances have been proposed in “Self-similarity driven color demosaicing,” by A. Buades, IEEE TIP, Vol. 18, No. 6, June 2009, pp. 1192-1202. F. Baqai et al. proposed patch-based L1 distances to measure local image similarity in “A Method to Measure Local Image Similarity Based on the L1 Distance Measure”, U.S. patent application Ser. No. 12/567,454, filed on Sep. 25, 2009.
Another critical part of the local image similarity measure is the threshold at which a pixel or an image patch is considered to be similar. The selection of a threshold is based on various factors such an estimate of the degree of degradation in the image, similarity criterion, distance metric (L1, L2, and others), and patch size. F. Baqai et al. utilize a relationship between distances measures to estimate appropriate thresholds in “A Method to Measure Local Image Similarity Based on the L1 Distance Measure”, cited above. Such a threshold can be represented as a product of the standard error sigma of local image intensities and a constant t that is not related to sigma and determined by some factors, but not limited to, such as patch sizes and pixel-similarity rates.
Note that standard error sigma of local image intensities is unknown and has to be estimated from image data. Such estimations are generally not perfect. To achieve a better similarity measurement, X. Dong et al. propose an improved procedure in “An Improved Method To Measure Local Image Similarity And Its Application In Image Processing”, U.S. patent application Ser. No. 12/931,962, filed on Feb. 15, 2011. The procedure selects one target image patch a time and calculates an intermediate result for the selected target patch. After processing all possible target patches, it then utilizes an intermediate result combining techniques to achieve better final results. A rotated storage technique is also used to improve the memory efficiency of the procedure.
As previously discussed, a specially designed wavelet transform on incomplete data such as output of a full color image sensor overlaid with CFA has inherent advantage in many image processing tasks since it avoids the estimation errors from demosaicing process. Adopting such specially designed wavelet transforms in an improved local image similarity measurement procedure will further improve the performance of many image processing tasks.